Число Грэма

Число Грэма (англ. Graham's number) — гигантское число, которое является верхней границей для решения определённой проблемы в теории Рамсея. Является некоторой очень большой степенью тройки, которая записывается с помощью нотации Кнута. Названо в честь Рональда Грэма.

Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке «Математические игры» в журнале Scientific American в ноябре 1977 года, где было сказано: «В неопубликованном доказательстве Грэм недавно установил границу настолько большую, что ей принадлежит рекорд как наибольшему числу, когда-либо использовавшемуся в серьёзном математическом доказательстве».

В 1980 году Книга рекордов Гиннесса повторила утверждения Гарднера, ещё больше подогрев интерес публики к этому числу. Число Грэма в невообразимое количество раз больше, чем другие хорошо известные большие числа, такие, как гугол, гуголплекс и даже больше, чем число Скьюза и число Мозера. Вся наблюдаемая вселенная слишком мала для того, чтобы вместить в себя обыкновенную десятичную запись числа Грэма (предполагается, что запись каждой цифры занимает по меньшей мере объём Планка). Даже степенные башни вида $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ бесполезны для этой цели (в том же смысле), хотя это число и может быть записано с использованием рекурсивных формул, таких, как нотация Кнута или эквивалентных, что и было сделано Грэмом. Последние 500 цифр числа Грэма — это

...02425950695064738395657479136519351798334535362521
   43003540126026771622672160419810652263169355188780
   38814483140652526168785095552646051071172000997092
   91249544378887496062882911725063001303622934916080
   25459461494578871427832350829242102091825896753560
   43086993801689249889268099510169055919951195027887
   17830837018340236474548882222161573228010132974509
   27344594504343300901096928025352751833289884461508
   94042482650181938515625357963996189939679054966380
   03222348723967018485186439059104575627262464195387.

В современных математических доказательствах иногда встречаются числа, ещё много бо́льшие, чем число Грэма, например, в работе с конечной формой Фридмана в теореме Краскала — так называемое TREE(3).

Проблема Грэма

Пример: 2 цвета и 3-мерный куб, содержащий один одноцветный 4-вершинный копланарный полный подграф. Подграф показан ниже куба. Этот куб не будет содержать такой подграф, если, например, нижний край у настоящего подграфа будет заменен на синий — что доказывает с помощью контрпримера, что N* > 3.

Число Грэма связано со следующей проблемой в теории Рамсея:

Рассмотрим $n$-мерный гиперкуб и соединим все пары вершин для получения полного графа с $2^{n}$ вершинами. Раскрасим каждое ребро этого графа либо в красный, либо в синий цвет. При каком наименьшем значении $n$ каждая такая раскраска обязательно содержит раскрашенный в один цвет полный подграф с четырьмя вершинами, все из которых лежат в одной плоскости?

Грэм и Ротшильд в 1971 году доказали, что эта проблема имеет решение, $N^{*}$, и показали, что $6\leqslant N^{*}\leqslant N$, где $N$ — конкретное, точно определённое, очень большое число. На языке стрелочной нотации Кнута оно может быть записано как $N=F^{7}(12)$, где $F(n)=2\uparrow ^{n}3$. Это число именуется как «малое число Грэма» (англ. Little Graham).

Нижняя граница была улучшена Экзу в 2003 году и Баркли в 2008 году, который показал, что $N^{*}$ должно быть не меньше 13. Потом последовало и улучшение верхней границы до $2\uparrow ^{3}6$ и затем до $2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$. Таким образом, $13\leqslant N^{*}\leqslant 2\uparrow \uparrow 2\uparrow \uparrow 2\uparrow \uparrow 9$.

Предметом настоящей статьи является верхняя граница $G$, которая много слабее (то есть больше), чем $N$: $G=f^{64}(4)$, где $f(n)=3\uparrow ^{n}3$. Именно эта граница, описанная в неопубликованной работе Грэма, и была описана (и названа числом Грэма) Мартином Гарднером.

Определение числа Грэма

При использовании Стрелочной нотации Кнута число Грэма G может быть записано как

$\left.{\begin{matrix}G&=&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow } 3\\&&3\underbrace {\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow } 3\\&&\underbrace {\qquad \;\;\vdots \qquad \;\;} \\&&3\underbrace {\uparrow \uparrow \cdots \cdot \cdot \uparrow } 3\\&&3\uparrow \uparrow \uparrow \uparrow 3\end{matrix}}\right\}{\text{64 слоя}}$,

где количество стрелок в каждом слое, начиная с верхнего, определяется числом в следующем слое, то есть

$G=g_{64},$ где $g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,$

где верхний индекс у стрелки показывает общее количество стрелок. Другими словами, $G$ вычисляется в 64 шага: на первом шаге мы вычисляем $g_{1}$ с четырьмя стрелками между тройками, на втором — $g_{2}$ с $g_{1}$ стрелками между тройками, на третьем — $g_{3}$ с $g_{2}$ стрелками между тройками и так далее; в конце мы вычисляем $G=g_{64}$ с $g_{63}$ стрелок между тройками.

Это может быть записано как

$G=f^{64}(4)$, где $f(n)=3\uparrow ^{n}3,$

где верхний индекс у $f$ означает итерации функций. Функция $f$ является частным случаем гипероператоров $f(n)={\text{hyper}}(3,n+2,3)$ и может также быть записана при помощи цепных стрелок Конвея как $f(n)=3\rightarrow 3\rightarrow (n+2)$. Последняя запись также позволяет записать следующие граничные значения для $G$:

$3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2.$

С помощью массивной нотации Бауэрса границы числа Грэма можно записать как:

{3,64,1,2} < G < {3,65,1,2}.

Масштаб числа Грэма

Для того чтобы осознать размер числа Грэма, полезно попробовать представить через возведение в степень хотя бы первый член (g₁) стремительно растущей 64-членной последовательности (т. н. «грааль», Grahal). На языке тетраций $\uparrow \uparrow$ означает:

$g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow {\Bigl (}3\uparrow \uparrow {\bigl (}3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots {\bigr )}{\Bigr )}$,

где число троек в выражении справа

$3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3).$

Теперь каждая тетрация ($\uparrow \uparrow$) по определению разворачивается в «степенную башню» как

$3\uparrow \uparrow X\ =\ 3\uparrow {\Bigl (}3\uparrow {\bigl (}3\uparrow \dots (3\uparrow 3)\dots {\bigr )}{\Bigr )}\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}$, где X — количество троек.

Таким образом,

$g_{1}=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots ))$, где количество троек — $3\uparrow \uparrow (3\uparrow \uparrow 3)$.

Оно может быть записано на языке степеней:

$g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3\quad$, где число башен — $\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3$,

где количество троек в каждой башне, начиная слева, указывается предыдущей башней.

Другими словами, $g_{1}$ вычисляется путём вычисления количества башен, $n=3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}$ (где число троек — $3^{3^{3}}$ = 7 625 597 484 987), и затем вычисления $n$ башен в следующем порядке:

1-я башня: 3

2-я башня: 3↑3↑3 (количество троек — 3) = 7 625 597 484 987

3-я башня: 3↑3↑3↑3↑…↑3 (количество троек — 7 625 597 484 987) = …

.

.

.

$g_{1}$ = $n$-я башня: 3↑3↑3↑3↑3↑3↑3↑…↑3 (количество троек задаётся результатом вычисления $(n-1)$-й башни)

Масштаб первого члена, $g_{1}$, настолько велик, что его практически невозможно осознать, хотя запись выше относительно проста для понимания. Хотя $n$ — это всего лишь количество башен в этой формуле для $g_{1}$, уже это число много больше количества объёмов Планка, которые содержатся в наблюдаемой вселенной (примерно $4\cdot 10^{185}$). Оно уже больше гуголплекса, и вся запись с 7625597484987 тройками уже на третьей башне (так называемое «тритри», Tritri) будет занимать расстояние от Земли до Солнца. Даже башня с четырьмя тройками $3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\approx 1{,}3\times 10^{3\,638\,334\,640\,024}$ представляет собой уже слишком большое число, чтобы представить его непосредственно. После первого члена нас ожидают ещё 63 члена стремительно растущей последовательности.

См. также

• Число Райо
• TREE(3)
• Большие числа

Литература

• Graham, R. L.; Rothschild, B. L. Ramsey's Theorem for n-Parameter Sets (англ.) // Transactions of the American Mathematical Society. — 1971. — Vol. 159. — P. 257—292. — doi:10.2307/1996010. The explicit formula for N appears on p. 290.
• Graham, R. L.; Rothschild, B.L. (1978). «Ramsey Theory», Studies in Combinatorics, Rota, G.-G., ed., Mathematical Association of America, 17:80-99. On p. 90, in stating «the best available estimate» for the solution, the explicit formula for N is repeated from the 1971 paper.
• Gardner, Martin. Mathematical Games (англ.) // Scientific American. — Springer Nature, 1977. — November (vol. 237). — P. 18—28.; reprinted (revised 2001) in the following book:
• Martin Gardner. The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems (англ.). — New York, NY: Norton, 2001. — ISBN 0393020231.
• Martin Gardner. Penrose Tiles to Trapdoor Ciphers (неопр.). — Washington, D.C.: Mathematical Association of America, 1989. — ISBN 0-88385-521-6.
• Exoo, Geoffrey. A Euclidean Ramsey Problem (неопр.) // Discrete Computational Geometry. — 2003. — Т. 29. — С. 223—227. — doi:10.1007/s00454-002-0780-5.

Ссылки

• Число Грэма на пальцах
• «Проблема Рамсея о гиперкубах». Geoff Exoo (англ.)
• Weisstein, Eric W. Graham’s number (англ.) на сайте Wolfram MathWorld.
• Как вычислить число Грэма (англ.)
• Numeropedia — the Special Encyclopedia of Numbers (англ.)